package com.company.algo.niuke;

import java.util.HashMap;
import java.util.Map;

public class FoundOnceNumber {
    public int foundOnceNumber1 (int[] arr, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i:arr){
            map.put(i,map.getOrDefault(i,0)+1);
            if(map.get(i)==k){
                map.remove(i);
            }
        }
        return map.keySet().iterator().next();
    }
    //位运算：出现k(奇数)次的数字每个位（0或者1）也是出现k(奇数)次，因此可以每一位的和能够被k整除（对k取余为0）
    public int foundOnceNumber (int[] arr, int k) {
        int[] binarySum = new int[32];      //int型二进制表示最多为32位，4字节
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            for(int num:arr){
                sum += (num>>i & 1);        //依次右移num，同1相与，计算每一位上1的个数
            }
            binarySum[i] = sum;
        }
        int res = 0;
        for (int i = 0; i < 32; i++) {
            if (binarySum[i]%k != 0){
                res += 1<<i;                //左移恢复
            }
        }
        return res;
    }


    public static void main(String[] args) {
        FoundOnceNumber Main = new FoundOnceNumber();
        int[] arr = {5,4,1,1,5,1,5};
        System.out.println(Main.foundOnceNumber(arr, 3));
    }
}
